package awk.datastruct.sort;

import java.util.Arrays;

/**
 *
 * @author haifeng.wang
 * @since 2019-07-02-17:04
 */      
public class StraightInsertionSort {

  /**
   * Title: 直接插入排序 ，依赖于初始序列
   * Description: 在有序序列中不断插入新的记录以达到扩大有序区到整个数组的目的
   * 				时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
   * 				空间复杂度：O(1)
   * 				稳    定   性：稳定
   * 				内部排序(在排序过程中数据元素完全在内存)
   */
  public static int[] straightInsertionSort(int[] target){
    if(target != null && target.length != 1){
      // 不断扩大有序序列，直到扩展到整个数组
      for (int i = 1; i < target.length; i++) {
        // 向有序序列中插入新的元素
        for (int j = i; j > 0; j--) {
          if(target[j]  < target[j-1]){
            // 交换
            int temp = target[j];
            target[j] = target[j-1];
            target[j-1] = temp;
          }
        }
      }
    }
    return target;
  }


  /**
   * Title: 折半插入排序，依赖于初始序列
   * Description:
   * 折半搜索出插入位置，并直接插入;与直接插入搜索的区别是，后者的搜索要快于顺序搜索
   * 时间复杂度：折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。
   * 所以，折半插入排序和插入排序的时间复杂度相同都是O（N^2），在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。
   * 空间复杂度：O(1)
   * 稳    定   性：稳定
   * 内部排序(在排序过程中数据元素完全在内存)
   */
  public static int[] binaryInsertSort(int[] target) {
    if (target != null && target.length > 1) {
      for (int i = 1; i < target.length; i++) {
        int left = 0;
        int right = i - 1;
        int mid;
        int temp = target[i];
        // 当前值小于有序序列的最大值时，开始查找插入位置
        if (temp < target[right]) {
          while (left <= right) {
            mid = (left + right) / 2;
            if (target[mid] < temp) {
              // 缩小插入区间
              left = mid + 1;
            } else if (target[mid] > temp) {
              // 缩小插入区间
              right = mid - 1;
            } else {
              // 待插入值与有序序列中的target[mid]相等，保证稳定性的处理
              left = left + 1;
            }
          }

          // left及其后面的数据顺序向后移动，并在left位置插入
          for (int j = i; j > left; j--) {
            target[j] = target[j - 1];
          }
          target[left] = temp;
        }
      }
    }
    return target;
  }


  /**
   *
   * Title: 希尔插入排序
   * Description: 分别对间隔为gap的gap个子序列进行直接插入排序，不断缩小gap,直至为 1
   *
   * 				刚开始时，gap较大，每个子序列元素较少，排序速度较快；
   * 				待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。
   *
   * 				时间复杂度：O(n) ~ O(n^2)
   * 				空间复杂度：O(1)
   * 				稳    定   性：不稳定
   * 				内部排序(在排序过程中数据元素完全在内存)
   */
  public static int[] shellSort(int[] target){
    if(target != null && target.length != 1){
      // gap个大小为gap的子序列
      int gap = target.length;
      do{
        // 不断缩小gap直至为1
        gap = gap/3 + 1;
        // 对每个子序列进行直接插入排序
        for (int i = 0 + gap; i < target.length; i++) {
          if(target[i] < target[i-gap]){
            int j = i - gap;
            // 待插入值
            int temp = target[i];
            do{
              // 后移元素
              target[j + gap] = target[j];
              // 再比较前一个元素
              j = j - gap;

            }
            // 向前比较的终止条件
            while(j >= 0 && target[j] > temp);
            // 将待插入值插入合适的位置
            target[j + gap] = temp;
          }
        }
      }while(gap > 1);
    }
    return target;
  }



  /**
   * Title: 交换排序中的冒泡排序，最多进行n-1次比较
   * Description: 因为越大的元素会经由交换慢慢"浮"到数列的顶端(最后位置)，最大的数最后才确定下来，所以称为冒泡排序
   * 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
   * 空间复杂度：O(1)
   * 稳 定 性：稳定
   * 内部排序(在排序过程中数据元素完全在内存)
   */
  public static int[] bubbleSort(int[] target) {
    int n = target.length;
    if ( n != 1) {
      // 最多需要进行n-1躺，每一趟将比较小的元素移到前面，比较大的元素自然就逐渐沉到最后面了，这就是冒泡
      for (int i = 0; i < n - 1; i++) {
        for (int j = n - 1; j > i; j--) {
          if (target[j] < target[j - 1]) {
            int temp = target[j];
            target[j] = target[j - 1];
            target[j - 1] = temp;
          }
        }
        System.out.println(Arrays.toString(target));
      }
    }
    return target;
  }


  /**
   * Title: 选择排序中的直接选择排序
   * Description: 每次找到数组中当前排序范围中的最小值并与该范围中的第一个数字交换，同时缩小待排序数组的排序范围
   * 时间复杂度：最好情形O(n^2)，平均情形O(n^2)，最差情形O(n^2)
   * 空间复杂度：O(1)
   * 稳    定   性：不稳定
   * 内部排序(在排序过程中数据元素完全在内存)
   */
  public static int[] straightSelectSort(int[] target) {

    if (target != null && target.length != 1) {
      for (int i = 0; i < target.length; i++) {
        int min_index = i;
        for (int j = i + 1; j < target.length; j++) {
          if (target[min_index] > target[j]) {
            min_index = j;
          }
        }
        // 导致不稳定的因素：交换
        if (target[min_index] != target[i]) {
          int min = target[min_index];
          target[min_index] = target[i];
          target[i] = min;
        }
      }
    }
    return target;
  }

  /**
   * Title:快速排序的变形
   * Description: 本质上不断调用经典快排的划分算法
   * 依次以数组中的每个元素为基准点进行划分，
   * 直到遍历所有元素都
   */
  public void quicksort(int[] array) {
    if (array != null && array.length != 0) {
      for (int i = 0; i < array.length; i++) {
        // 以下是快排的划分算法
        int base_index = 0;
        int base = array[i];
        base_index = i;
        for (int j = i+1; j < array.length; j++) {
          if (array[j] <= base ) {
            base_index ++;
            if (base_index != j) {
              int temp = array[base_index];
              array[base_index] = array[j];
              array[j] = temp;
            }
          }
        }
        array[i] = array[base_index];
        array[base_index] = base;
        System.out.println(Arrays.toString(array));
      }
    }
  }

  /**
   * Title: 分配排序中的基数排序
   * Description: 不是在对元素进行比较的基础上进行排序，而是采用 "分配 + 收集" 的办法
   *
   * 				首先，将目标序列各元素分配到各个桶中；
   * 				其次，将各个桶中的元素按先进先出的顺序再放回去
   * 				如此往复...
   *
   * 				时间复杂度：O(d*(r+n))或者 O(dn),d 的大小一般会受到 n的影响
   * 				空间复杂度：O(rd + n)或者 O(n)
   * 				稳    定   性：稳定
   * 				内部排序(在排序过程中数据元素完全在内存)
   *  分配 + 收集
   * @param target 待排序数组
   * @param r 基数
   * @param d 元素的位数
   * @param n 待排序元素个数
   * @return
   */
  public static int[] radixSort(int[] target, int r, int d, int n){
    if (target != null && target.length != 1 ) {

      // 一共有基数r个桶，每个桶最多放n个元素
      int[][] bucket = new int[r][n];
      // 获取元素对应位上的数字，即装入那个桶
      int digit;
      // 定义每一轮的除数，1, 10, 100, ...
      int divisor = 1;
      // 统计每个桶中实际存放元素的个数
      int[] count = new int[r];
      // d 位的元素，需要经过分配、收集d次即可完成排序
      for (int i = 0; i < d; i++) {

        // 分配
        for (int ele : target) {
          // 获取元素对应位上的数字(巧妙！！！)
          digit = (ele/divisor) % 10;
          // 将元素放入对应桶，桶中元素数目加1
          bucket[digit][count[digit]++] = ele;
        }

        //  目标数组的下标
        int index = 0;
        for (int j = 0; j < r; j++) {
          // 用于按照先进先出顺序获取桶中元素
          int k = 0;
          while(k < count[j]){
            // 按照先进先出依次取出桶中的元素
            target[index++] = bucket[j][k++];
          }
          // 计数器归零
          count[j] = 0;
        }
        //用于获取元素对应位数字
        divisor *= 10;
      }
    }
    return target;
  }

}